class Solution {
    int[][] memo;
    public int getMoneyAmount(int n) {
        memo = new int[n + 2][n + 2];
        return dfs(1, n);
    }
    public int dfs(int i, int j){
        if(i >= j) return 0;
        if(memo[i][j] != 0) return memo[i][j];
        int ret = Integer.MAX_VALUE;
        for(int k = i; k <= j; k++){
            // 左子树
            int l = dfs(i, k - 1);
            // 右子树
            int r = dfs(k + 1, j);
            int tmp = Math.max(l, r) + k;
            ret = Math.min(ret, tmp);
        }
        memo[i][j] = ret;
        return ret;
    }
}